/*
LeetCode 60

60. 排列序列
困难
相关标签
相关企业
给出集合 [1,2,3,...,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。

 

示例 1：

输入：n = 3, k = 3
输出："213"
示例 2：

输入：n = 4, k = 9
输出："2314"
示例 3：

输入：n = 3, k = 1
输出："123"
 

提示：

1 <= n <= 9
1 <= k <= n!
*/

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string getPermutation(int n, int k) {
        // 计算所有排列的阶乘
        vector<int> fact(n, 1);
        for (int i = 2; i < n; i++) {
            fact[i] = fact[i - 1] * i;
        }
        // 数字集合init
        vector<char> nums;
        for (int i = 1; i <= n; i++)
            nums.push_back(i + '0');
    
        // k 的值要变，题目是1-base索引，与数组索引差1
        k--;
    
        // 结果的构建
        string ans = "";
        for (int i = n; i >= 1; i--) {
            // 当前位
            int index = k / fact[i - 1];
            ans += nums[index];
            nums.erase(nums.begin() + index); // 已经使用的数字就出去
            k %= fact[i - 1];                 // k 更新
        }
        return ans;
    }
};